package 动态链表;

import 动态数组.线性表.List;
import 动态数组.队列.接口.Deque;
import 动态数组.栈.接口.Stack;

import java.util.Comparator;
import java.util.Iterator;
import java.util.Objects;

public class LinkedList<E> implements List<E>, Deque<E>, Stack<E> {
    private class Node{
        E data;
        //前一个节点
        Node pre;
        //后一个节点
        Node next;

        public Node(){
            this(null, null, null);
        }

        public Node(E data){
            this(data,null,null);
        }

        public Node(E data, Node pre, Node next){
            this.data = data;
            this.pre = pre;
            this.next = next;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }

    private Node head;
    private Node tail;
    private int size;

    public LinkedList(){
        head = null;
        tail = null;
        size = 0;
    }

    public LinkedList(E[] arr){
        for (int i = 0; i < arr.length; i++) {
            add(arr[i]);
        }
    }
    @Override
    public void add(E element) {
        add(size,element);
    }

    @Override
    public void add(int index, E element) {
        if (index < 0 || index > size){
            throw new IllegalArgumentException("add index out of the range");
        }
        Node node = new Node(element);
        //分为空，表头插入，表尾插入，中间插入
        if (isEmpty()){
            head = node;
            tail = node;
            tail.next = head;
            head.pre = tail;
        }else if (index == 0){
            node.pre = head.pre;
            node.next = head;
            head.pre = node;
            head = node;
            tail.next = head;
        }else if(index == size){
            node.next = tail.next;
            tail.next = node;
            node.pre = tail;
            tail = node;
            head.pre = tail;
        }else{
            Node p,q;
            //中间插入分左边和右边的插入
            if (index <= size / 2){
                p = head;
                for (int i = 0; i < index - 1; i++) {
                    p = p.next;
                }
                q = p.next;
                p.next = node;
                node.pre = p;
                q.pre = node;
                node.next = q;
            }else {
                p = tail;
                for (int i = size - 1; i > index; i--) {
                    p = p.pre;
                }
                q = p.pre;
                q.next = node;
                node.pre = q;
                node.next = p;
                p.pre = node;
            }
        }
        size++;
    }

    @Override
    public void remove(E element) {
        int index = indexOf(element);
        if (index != -1){
            remove(index);
        }

    }

    @Override
    public E remove(int index) {
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("remove index out of the range");
        }
        Node node = null;
        E ret = null;
        if (size == 1){
            ret = head.data;
            head = null;
            tail = null;
        }else if (index == 0){
            ret = head.data;
            node = head.next;
            head.next = null;
            node.pre = head.pre;
            head.pre = null;
            head = node;
            tail.next = head;
        }else if (index == size - 1){
            ret = tail.data;
            node = tail.pre;
            tail.pre = null;
            node.next = tail.next;
            tail.next = null;
            tail = node;
            head.pre = tail;
        }else {
            Node p,q,r;
            if (index <= size / 2){
                p = head;
                for (int i = 0; i < index - 1; i++) {
                    p = p.next;
                }
                q = p.next;
                ret = q.data;
                r = q.next;
                p.next = r;
                r.pre = p;
                q.pre = null;
                q.next = null;
            }else {
                p = tail;
                for (int i = size - 1; i > index + 1; i--) {
                    p = p.pre;
                }
                q = p.pre;
                ret = q.data;
                r = q.pre;
                r.next = p;
                p.pre = r;
                q.next = null;
                q.pre = null;
            }
        }
        size--;
        return ret;
    }

    @Override
    public E get(int index) {
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("get index out of the range");
        }
        //返回角标0
        if (index == 0){
            return head.data;
        }else if (index == size - 1){
            return tail.data;
        }else {
            Node p = head;
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
            return p.data;
        }
    }

    @Override
    public E set(int index, E element) {
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("get index out of the range");
        }
        //返回角标0
        E ret = null;
        if (index == 0){
            ret = head.data;
            head.data = element;
        }else if (index == size - 1){
            ret = tail.data;
            tail.data = element;
        }else {
            Node p = head;
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
            ret = p.data;
            p.data = element;
        }
        return ret;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public int indexOf(E element) {
        return indexOf(head,element,0);
    }

    private int indexOf(Node root,E key,int index){
        if (root == null){
            return  -1;
        }
        if (root.data.equals(key)){
            return index;
        }
        if (root.next == head){
            return -1;
        }
        return indexOf(root.next, key, ++index);
    }

    @Override
    public boolean contains(E element) {
        return indexOf(element) != -1;
    }

    @Override
    public boolean isEmpty() {
        return size == 0 && head == null && tail == null;
    }

    @Override
    public void clear() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        if (isEmpty()){
            sb.append(']');
        }else {
            Node node = head;
            while (true){
                sb.append(node.data);
                if (node == tail){
                    sb.append(']');
                    break;
                }else {
                    sb.append(',');
                }
                node = node.next;
            }
        }
        return sb.toString();
    }

    @Override
    public void sort(Comparator<E> c) {
        /**
         * 插入排序
         */
        if (c == null){
            throw new IllegalArgumentException("Comparator can not be null");
        }
        if (size < 2){
            return;
        }
        Node p = head.next;
        Node a = null;
        Node b = null;
        E e = null;
        while (p != head){
            a = p;
            b = a.pre;
            e = p.data;
            while (b != tail && c.compare(b.data, e) > 0){
                a.data = b.data;
                a = a.pre;
                b = b.pre;
            }
            a.data = e;
            p = p.next;
        }
        /**
         * 选择排序
         */
//        if (c == null){
//            throw new IllegalArgumentException("comparator can not be null");
//        }
//        Node nodeA = head;
//        Node nodeB = nodeA.next;
//        while (true) {
//            while (true) {
//                if (c.compare(nodeA.data,nodeB.data) > 0) {
//                    E e = nodeA.data;
//                    nodeA.data = nodeB.data;
//                    nodeB.data = e;
//                }
//                nodeB = nodeB.next;
//                if (nodeB == head) { // change code
//                    break;
//                }
//            }
//            if (nodeA.next == tail) {
//                break;
//            }
//            nodeA = nodeA.next;
//            nodeB = nodeA.next;
//        }
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        if (fromIndex < 0 || toIndex >= size || fromIndex > toIndex){
            throw new IllegalArgumentException("index was error");
        }
        LinkedList<E> newList = new LinkedList<>();
        //定义到fromIndex的节点
        Node nodeA = head;
        for (int i = 0; i < fromIndex; i++) {
            nodeA = nodeA.next;
        }
        //定义到toIndex的节点
        Node nodeB = head;
        for (int i = 0; i < toIndex; i++) {
            nodeB = nodeB.next;
        }
        Node p = nodeA;
        while (p != nodeB){
            newList.add(p.data);
            p = p.next;
        }
        return newList;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        LinkedList<E> other = (LinkedList<E>) obj;
        if (size == other.size){
            for (int i = 0; i < size; i++) {
                if (get(i) != other.get(i)){
                    return false;
                }
            }
        }else {
            return false;
        }

        return true;
    }

    @Override
    public int hashCode() {
        return Objects.hash(head, tail, size);
    }

    @Override
    public Iterator<E> iterator() {
        return new LinkedListIterator();
    }

    class LinkedListIterator implements Iterator<E>{
        private Node cur = head;
        private boolean flag = true; //表示是否为第一圈

        @Override
        public boolean hasNext() {
            return flag;
        }

        @Override
        public E next() {
            E ret = cur.data;
            cur = cur.next;
            if (cur == head){
                flag = false;
            }
            return ret;
        }
    }

    @Override
    public void addFirst(E element) {
        add(0,element);
    }

    @Override
    public void addLast(E element) {
        add(size,element);
    }

    @Override
    public E removeFirst() {
        return remove(0);
    }

    @Override
    public E removeLast() {
        return remove(size - 1);
    }

    @Override
    public E getFirst() {
        return get(0);
    }

    @Override
    public E getLast() {
        return get(size - 1);
    }

    @Override
    public void push(E element) {
        addLast(element);
    }

    @Override
    public E pop() {
        return removeLast();
    }

    @Override
    public E peek() {
        return getLast();
    }

    @Override
    public void offer(E element) {
        addLast(element);
    }

    @Override
    public E poll() {
        return removeFirst();
    }

    @Override
    public E element() {
        return getFirst();
    }

}
